package mao.leetcode.dp.leetcode62;

import java.util.Arrays;

public class Solution {

    //动态规划
    public int uniquePaths_1(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j]+=cur[j-1];
            }
        }
        return cur[n-1];
    }


    //精度不够，不能用
    public int uniquePaths(int m, int n) {
       if (m>n) return C(m+n-2,n-1);
       else return C(m+n-2,m-1);
    }

    public int C(int n,int m){
        double result=1;
        for (int i = m; i>0; i--) {
            result=result*n/i;
            n--;
        }
        return (int)result;
    }

}
